package sort.memory;

import java.util.Arrays;

public class ShellSortLinked {
    public static void main(String[] args) {

        int[] array = SortUtil.newArray(10000);
        System.out.println(Arrays.toString(array));

        ListNode head = SortUtil.toLinked(array);
        ShellSortLinked solution = new ShellSortLinked();
        solution.sortList(head);

        SortUtil.print(head);
    }

    public ListNode sortList(ListNode head) {
        int length = 0;
        for (ListNode start = head; start != null; start = start.next) {
            length++;
        }

        //希尔排序
        for (int skip = length / 2; skip > 0; skip /= 2) {
            insertSort(head, skip);
        }

        return head;
    }

    /**
     * 插入排序
     * @param head
     * @param skip
     */
    public void insertSort(ListNode head, int skip) {
        ListNode start = head;
        for (int i = 0; i < skip; i++) {
            insertSortSegment(start, skip);
            start = start.next;
        }
    }

    /**
     * 对start所在的单个分组的插入排序
     * @param start
     * @param skip
     */
    public void insertSortSegment(ListNode start, int skip) {
        //insertNode需要插入的节点
        for (ListNode insertNode = skip(start, skip); insertNode != null; insertNode = skip(insertNode, skip)) {
            //和本分组所有前面节点比较，这里单向连表遍历对希尔排序不优化，因为从后往前比较可以提前中止来提高性能
            for (ListNode preCompare = start; preCompare != insertNode; preCompare = skip(preCompare, skip)) {
                compareAndSwap(preCompare, insertNode);
            }
        }
    }

    /**
     * 在node跳skip个间隔
     * @param node
     * @param skip
     * @return
     */
    public ListNode skip(ListNode node, int skip) {
        for (int i = 0; i < skip; i++) {
            node = node.next;
            if (node == null) {
                return null;
            }
        }
        return node;
    }

    public boolean compareAndSwap(ListNode n1, ListNode n2) {
        if (n2.val < n1.val) {
            int temp = n2.val;
            n2.val = n1.val;
            n1.val = temp;
            return true;
        }
        return false;
    }
}